package org.ala.everyday;

import java.util.*;

/**
 * 给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。
 *
 * 如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：
 *
 * num1 和 num2 都 在数组 nums 中存在。
 * num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。
 * 返回 不同 优质数对的数目。
 *
 * 如果 a != c 或者 b != d ，则认为 (a, b) 和 (c, d) 是不同的两个数对。例如，(1, 2) 和 (2, 1) 不同。
 *
 * 注意：如果 num1 在数组中至少出现 一次 ，则满足 num1 == num2 的数对 (num1, num2) 也可以是优质数对。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,1], k = 3
 * 输出：5
 * 解释：有如下几个优质数对：
 * - (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。
 * - (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
 * - (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
 * 所以优质数对的数目是 5 。
 * 示例 2：
 *
 * 输入：nums = [5,1,1], k = 10
 * 输出：0
 * 解释：该数组中不存在优质数对。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 109
 * 1 <= k <= 60
 *
 * @author ala
 * @date 2024-10-10 11:15
 */
public class Q2354 {

    public static void main(String[] args) {
        Q2354 q = new Q2354();

//        int[] nums = {1,2,3,1};
//        int k = 3;

//        int[] nums = {5,1,1};
//        int k = 10;

//        int[] nums = {1,2,3,1,536870911};
//        int k = 3;

        int[] nums = {559784392,286488512,179294707,492771529,397778898,860336062,825065433,917230184,241527107,504607432,74224062,93090298,662894082,715249108,54674327,879211921,656060803,188516319,59026056,558933075,773288071,903234121,798335412,520554417,337310717,156283837,327184294,151520534,269282045,67587756,820698746,451084794,348484389,924391489,512122305,38276909,898644577,54695609,960931989,876779227,94265785,616590758,507092039,650310538,843577857,805827283,460035041,446444932,496130926,546151967,543619479,104014596,782425152,626487138,341615244,312188212,51346522,719158638,423473329,384690205,852891087,909991598,174043740,698720591,950686624,133633211,223321531,832405066,23811343,591409374,831629155,231254673,307305643};
        int k = 47;

        System.out.println(q.countExcellentPairs(nums, k));
    }

    public long countExcellentPairs(int[] nums, int k) {
        return V1(nums, k);
    }
    /**
     *  1）bc(x|y) + bc(x&y) = bc(x) + bc(y)
     *      其中 bc 为 BitCount函数
     *      问题转换为：数组中每个数转换为二进制1的个数，统计和 >=k 的组合数
     *      构造数组：bcs[i] = bc(nums[i])
     *  2）从左往右遍历bcs，构造树状数组（32位int，最多32个1）
     *      往左加，往右查
     *      结果 * 2，累加到答案中
     */
    protected long V1(int[] nums, int k) {
        //  去重，并且在去重的过程中统计 (n,n) 的个数
        Set<Integer> set = new HashSet<>();
        List<Integer> bcs = new ArrayList<>();
        long res = 0;
        for (int n : nums) {
            if (set.add(n)) {
                int bc = Integer.bitCount(n);
                bcs.add(bc);

                if ((bc << 1) >= k) {
                    res += 1;
                }
            }
        }

        BitTree bt = new BitTree(32);
        for (int bc : bcs) {
            //  如果n的二进制位中，1的数量已经>=k，则之前遍历到的全部数据都满足要求
            res += bt.query(Math.max(k - bc, 1)) << 1;
            bt.update(bc);
        }
        return res;
    }
    static class BitTree {
        int[] tree;
        int N;
        public BitTree(int n) {
            this.N = n;
            tree = new int[n + 1];
        }
        public void update(int i) {
            for (int j = i ; j > 0 ; j -= j & -j) {
                tree[j]++;
            }
        }
        public int query(int i) {
            int sum = 0;
            for (int j = i ; j <= N ; j += j & -j) {
                sum += tree[j];
            }
            return sum;
        }
    }
}
